package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LCJZOF49 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 经典解法，每日一看
     * 凭啥，没看懂：为何别人的没有重复，我的有重复呢？
     * @return:
     */
    class Solution {
        public int nthUglyNumber(int n) {
            int[] uglyNum = new int[n + 1];
            int[] factor = {2, 3, 5};
            int[] factorPos = {1, 1, 1};
            uglyNum[1] = 1;

            for (int i = 2; i <= n; i++) {
                int curMinNum = Integer.MAX_VALUE, curMinIdx = 0;
                for (int j = 0; j < factor.length; j++) {
                    if (uglyNum[factorPos[j]] * factor[j] <= uglyNum[i - 1]) factorPos[j]++;//为何别人的没有重复，我的有重复呢？
                    if (uglyNum[factorPos[j]] * factor[j] < curMinNum) {
                        curMinNum = uglyNum[factorPos[j]] * factor[j];
                        curMinIdx = j;
                    }
                }

                uglyNum[i] = curMinNum;
                factorPos[curMinIdx]++;
            }

            return uglyNum[n];
        }
    }

    class SolutionX {
        public int nthUglyNumber(int n) {
            int p2 = 0, p3 = 0, p5 = 0;
            int[] dp = new int[n];
            dp[0] = 1;
            for (int i = 1; i < n; i++) {
                dp[i] = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
                if (dp[i] == dp[p2] * 2) p2++;
                if (dp[i] == dp[p3] * 3) p3++;//淦，此处可以达成去重的效果，如果有重复的书，三个if就可以去重，重复的数字指针都后移了
                if (dp[i] == dp[p5] * 5) p5++;
            }
            return dp[n - 1];
        }
        // 一个十分巧妙的动态规划问题
        // 1.我们将前面求得的丑数记录下来，后面的丑数就是前面的丑数*2，*3，*5
        // 2.但是问题来了，我怎么确定已知前面k-1个丑数，我怎么确定第k个丑数呢
        // 3.采取用三个指针的方法，p2,p3,p5
        // 4.index2指向的数字下一次永远*2，p3指向的数字下一次永远*3，p5指向的数字永远*5
        // 5.我们从2*p2 3*p3 5*p5选取最小的一个数字，作为第k个丑数
        // 6.如果第K个丑数==2*p2，也就是说前面0-p2个丑数*2不可能产生比第K个丑数更大的丑数了，所以p2++
        // 7.p3,p5同理
        // 8.返回第n个丑数

    }


    public void run() {
        Solution solution = new Solution();
        for (int i = 1; i < 20; i++) {
            System.out.println(i + " : " + solution.nthUglyNumber(i));
        }
    }

    public static void main(String[] args) throws Exception {
        LCJZOF49 an = new LCJZOF49();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
